package com.asia.algorithmcode.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @DESCRIPTION: 93 复原IP地址
 * @USER: wanfu
 * @DATE: 2025/4/23 星期三 16:32
 */
public class RestoreIpAddresses {


    public static void main(String[] args) {
        System.out.println(new RestoreIpAddresses().restoreIpAddresses("19216811"));
    }

    static int POINT_COUNT = 0;
    List<String> resList = new ArrayList<>();
    String tempStr = "";

    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0, "");
        return resList;
    }

    private void dfs(String s, int index, int u, String path) {
        if (index == s.length()) {
            if (u == 4) {
                path = path.substring(0, path.length() - 1);
                resList.add(path);
            }
            return;
        }
        if (u >= 4) { // 最多只有四个部分，比4个多的情况下可以直接结束
            return;
        }

        for (int i = index, t = 0; i < s.length(); i++) {
            if (i > index && s.charAt(index) == '0') break;
            t = t * 10 + s.charAt(i) - '0';
            if (t <= 255) {
                dfs(s, i + 1, u + 1, path + t + ".");
            }else break;
        }

    }

    /**
     * 个人实现的暴力搜索
     *
     * @param s
     * @param index
     */
    private void dfs(String s, int index) {
//        int zeroCount = 0;
//        for (char c : tempStr.toCharArray()) {
//            if (c == '.') {
//                zeroCount++;
//            }
//        }
        if (POINT_COUNT == 3
                && tempStr.length() == s.length() + 3
                && tempStr.substring(tempStr.length() - 1).equals(s.substring(s.length() - 1))) {
            if (!resList.contains(tempStr)) {
                resList.add(tempStr);
            }
            return;
        }
        if (index >= s.length() || POINT_COUNT > 3) {
            return;
        }
        String numStr = tempStr.lastIndexOf(".") >= 0
                ? tempStr.substring(tempStr.lastIndexOf(".") + 1) + s.charAt(index)
                : tempStr + s.charAt(index);
        if (numStr.length() > 1 && numStr.startsWith("0")) {
            return;
        }
        int num = Integer.parseInt(numStr);
        if (num > 255) {
            return;
        }
        tempStr = tempStr + s.charAt(index);
        dfs(s, index + 1);
        tempStr = tempStr + ".";
        POINT_COUNT++;
        dfs(s, index + 1);
        tempStr = tempStr.substring(0, tempStr.length() - 1);
        POINT_COUNT--;
        dfs(s, index + 1);
        tempStr = tempStr.substring(0, tempStr.length() - 1);

    }

}
